An Evolutionary Multi Label Classification using Associative Rule Mining for Spatial Preferences

Abstract

Multi-label spatial classification based on association rules with Multi objective genetic algorithms (MOGA) is proposed to deal with multiple class labels problem which is hard to settle by existing methods. In this paper we adapt problem transformation for the Multi label classification. We use Hybrid evolutionary algorithm for the optimization in the generation of spatial association rules, which addresses single label. MOGA is used to combine the single labels into multi labels with the conflicting objectives predictive accuracy and Comprehensibility. Finally we built the classifier with a sorting mechanism. The algorithm is executed and the results are compared with Decision trees and Neural network based classifiers, the proposed method out performs the existing.

Reference

• Richard Frank , Martin Ester , Arno Knobbe, A multi-relational approach to spatial classification, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France
• Koperski, K.: Progressive Refinement Approach to Spatial Data Mining,Ph.D. thesis,Computing Science, Simon Fraser University, (1999).
• Subhija Ponjavic, Elvir Ferhatbegović , Multi-Criteria Land Use Classification in GIS for Buildings Construction, 15th International Conference on Urban Planning and Regional Development in the Information Society, 18 - 20 MAY 2010, Reed Messe Wien, Vienna,Austria (pp.445-454)
• Li, W., Han, J., and Pei, J. CMAR: Accurate and efficient classification based on multiple class association rule mining. Proceedings of the ICDM’01 (pp. 369-376). San Jose, CA, 2001. [5] Liu,B., Hsu, W., and Ma, Y. Integrating classification and association rule mining. Proceedings of the KDD (pp 80-86), Newyork, 1998.
• Fadi A. Thabtah, Peter Cowling, Yonghong Peng, "MMAC: A New Multi-Class, Multi-Label Associative Classification Approach," ICDM, pp.217-224, Fourth IEEE International Conference on Data Mining (ICDM'04), 2004
• Yin, X. and Han, J.: CPAR: Classification Based on Predictive Association Rules. Proc SIAM Int Conf on Data Mining (SDM'03), 2003, 331-335
• Fadi Thabtah, Challenges and Interesting Research Directions in Associative Classification, Proceedings of the Sixth IEEE International Conference on Data Mining - Workshops, p.785-792, December 18-22, 2006.
• Satchidananda Dehuri, Sung-Bae Cho, "Multi-objective Classification Rule Mining Using Gene Expression Programming," iccit, vol. 2, pp.754-760, 2008 Third International Conference on Convergence and Hybrid Information Technology, 2008.
• Diansheng Guo, Jeremy Mennis, “Spatial data mining and geographic knowledge discovery – An introduction” , Computers, Environment and Urban Systems 33 (2009) 403–408.
• Ester, M., Kriegel, H. P., & Sander, J, “Spatial data mining: A database approach”, Advances in spatial databases (pp. 47–66). Berlin: Springer-Verlag Berlin. 1997.
• Koperski, K., Han, J., and Stefanovic, N., “ An efficient two-step method for classification of spatial data” , 1998 international symposium on spatial data handling SDH’98 (pp. 45–54), Vancouver, BC, Canada. 1998.
• Malerba, D., Esposito, F., Lanza, A., Lisi, F.A., Appice, A.: Empowering a GIS with Inductive Learning Capabilities: The Case of INGENS. Journal of Computers, Environment and Urban Systems, Elsevier Science, 27 . 265-281. 2003.
• Nadia Ghamrawi , Andrew McCallum, “Collective multi-label classification”, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
• Benhui Chen, Liangpeng Ma and Jinglu Hu, “An improved multi-label classification method based on svm with delicate decision boundary “ , International Journal of Innovative Computing, Information and Control , Volume 6, Number 4, pp. 1605–1614, April 2010.
• Tsoumakas, G., Katakis, I., Vlahavas, I.: “Mining Multi-label Data.”,Maimon, O., Rokach, L. (eds.) Data Mining and Knowledge Discovery Handbook, 2nd edn. Springer, Heidelberg ,2009.
• Brinker, K., Furnkranz, J., Hullermeier, E.: A unified model for multilabel classification and ranking. In: Proceedings of the 17th European Conference on Arti¯cialIntelligence (ECAI '06), Riva del Garda, Italy , pp 489-493, 2006
• Min-Ling Zhang and Zhi-Hua Zhou, “Ml-knn: A lazy learning approach to multi-label learning,” Pattern Recogn., vol. 40, no. 7, pp. 2038–2048, 2007.
• Weiwei Cheng and Eyke Hllermeier, “Combining instancebased learning and logistic regression for multilabel classification,” Machine Learning, vol. 76, no. 2-3, pp. 211–225, September 2009.
• Fayyad, U., Piatetsky-Shapiro, G., Smith, G. & Uthurusamy, R. 1998 Advances in Knowledge Discovery and Data Mining. Menlo Park, CA: AAAI Press.
• Thabtah F., Cowling P., and Peng Y. (2004): Multi-label Classification Learning, Proceedings of the IEEE 2004 International Conference on Advances in Intelligent Systems (AISTA ’04). Luxembourg, Luxembourg, pp. 207-213, Nov. 2004.
• W. Li, J. Han, and J. Pei. CMAR: Accurate and efficient classification based on multiple-class association rule. In Proceeding of the First IEEE International Conference on Data Mining (ICDM’01), pp. 369- 376, San Jose, CA, Nov. 2001.
• Yin, X. and Han, J.: CPAR: Classification Based on Predictive Association Rules. Proc SIAM Int Conf on Data Mining (SDM'03), 331-335, 2003.
• S. Dehuri et al, “Application of Elitist Multi-objective Genetic Algorithms for Classification Rule Generations,” Applied Soft Computing, vol. 8, no. 1, pp.477-487, 2008.
• S. Dehuri, S. Ghosh, and A. Ghosh, “Genetic Algorithms for Optimization of Multiple Objectives in Knowledge Discovery from large Databases,” A. Ghosh (Eds.), Multi-objective Evolutionary Algorithms for Knowledge Discovery from Databases, pp. 1-22, 2008.
• A. L. Corcoran and S. Sen, “Using Real-valued Genetic Algorithms to Evolve Rule Sets for Classification,” Proc. 1st IEEE Conf. Evolutionary Computation, pp. 120–124, June 1994.
• A . Colorni, M. Dorigo, and V. Maniezzo. Positive feedback as a search strategy. Technical Report No. 91-016, Politecnico di Milano, Italy,1991.
• A. Colorni, M. Dorigo, and V. Maniezzo . The ant system: an autocatatlytic process. Technical Report No. 91- 016, Politecnico di Milano, Italy, 1991.
• M. Dorigo. Optimization, Learning and Natural Algorithms. Ph.D. Thesis, Politecnico di Milano, Italy,1992
• R. Beckers, J.L. Deneubourg and S. Goss. Trails and Uturns in the selection of the shortest path by the ant lasius niger. Journal of Theoretical Biology, 159, 1992, pp. 397- 415.
• S. Goss, S. Aron, J.L. Deneubourg and J.M. Pasteels (). Self-organized shortcuts in the argentine ant. Naturwissenschaften, 76, 1989, pp. 579-581.
• B. Holldobler and E.O. Wilson (1990). The Ants. Springer-Verlag: Berlin.
• Dehuri, S., Mall, R. "Predictive and Comprehensible Rule Discovery Using A Multi-Objective Genetic Algorithm", Knowledge Based System, volume 19, pp: 413-421, 2006 (SCI).
• Xian-Jun Shi, Hong Lei , “ A Genetic Algorithm-Based Approach for Classification Rule Discovery”. International Conference on Information Management, Innovation Management and Industrial Engineering, 2008, Volume: 1, page(s): 175-178, 2008.
• Xinqi Zheng, Lu Zhao, “Association Rule Analysis of Spatial Data Mining Based on Matlab”, Workshop on Knowledge Discovery and Data Mining , 2008 IEEE DOI 10.1109/WKDD.2008.21
• Moses santhakumar et al, “Transportation system management for Madurai city using GIS”, Map India 2003.
• Aditi Pai and Deepika Khatri, “She buys to conquer”,India Today, April 25, 2008.

Index Terms

Key words